/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
#include <stdlib.h>
typedef struct Listnode{
    int val;
    struct Listnode* next;
}Listnode;

Listnode* BuyNewnode(int x)
{
    Listnode* newnode=(Listnode*)malloc(sizeof(Listnode));
    newnode->val=x;
    newnode->next=NULL;
    return newnode;
}

Listnode* CreatCirculate(int n)
{
    Listnode* head,*tail;
    head=tail= BuyNewnode(1);
    for(int i=2;i<=n;i++)
    {
        Listnode* newnode= BuyNewnode(i);
        tail->next=newnode;
        tail=tail->next;
    }
    tail->next=head;
    return tail;
}

int ysf(int n, int m ) {
    Listnode* prve=CreatCirculate(n);
    Listnode* pcur=prve->next;
    int count=1;
    while(pcur!=prve)
    {
        if(count == m)
        {
            count=1;
            prve->next=pcur->next;
            free(pcur);
            pcur=prve->next;
        }
        else
        {
            pcur=pcur->next;
            prve=prve->next;
            count++;
        }
    }
    int ret =pcur->val;
    free(pcur);
    pcur=prve=NULL;
    return ret;
}



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head){
    if( head==NULL ||head->next==NULL)
    return true;
    if(head->next->next==NULL)
    {
        if(head->val == head->next->val)
        return true;
        else
        return false;
    }
    ListNode *slow,*fast;
    slow=fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    if(fast && fast->next)
    {
        slow=slow->next;
    }
    ListNode *p1=slow;
    ListNode *p2=p1->next;
    ListNode *p3=p2->next;
    while(p2)
    {
        p2->next=p1;
        p1=p2;
        p2=p3;
        if(p3)
        p3=p3->next;
    }
    ListNode *left=head;
    ListNode *right=p1;
    while(left!=slow)
    {
        if(left->val != right->val)
        return false;
        else
        {
            left=left->next;
            right=right->next;
        }
    }
    return true;
}

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode *pa=headA;
    ListNode *pb=headB;
    while(pa != pb)
    {
        pa=pa==NULL?headB:pa->next;
        pb=pb==NULL?headA:pb->next;
    }
    return pa;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;

ListNode *buynewnode(x)
{
    ListNode *newnode=(ListNode*)malloc(sizeof(ListNode));
    newnode->val=x;
    newnode->next=NULL;
    return newnode;
}

ListNode *reverse(ListNode* ls)
{
    if(ls==NULL ||ls->next == NULL)
    {
        return ls;
    }
    ListNode *p1=NULL;
    ListNode *p2=ls;
    ListNode *p3=p2->next;
    while(p2)
    {
        p2->next=p1;
        p1=p2;
        p2=p3;
        if(p3)
        p3=p3->next;
    }
    return p1;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if(l1->val == 0 && l1->next == NULL)
    return l2;
    if(l2->val == 0 && l2->next == NULL)
    return l1;
    ListNode *newl1=reverse(l1);
    ListNode *newl2=reverse(l2);
    unsigned long int val1=0,val2=0;
    ListNode *p1=newl1;
    ListNode *p2=newl2;
    while(p1)
    {
        val1=val1*10+(p1->val);
        p1=p1->next;
    }
    while(p2)
    {
        val2=val2*10+(p2->val);
        p2=p2->next;
    }
    unsigned long int sum=val1+val2;
    ListNode *newHead,*newTail;
    newHead=newTail=(ListNode*)malloc(sizeof(ListNode));
    while(sum)
    {
        ListNode *newnode=buynewnode(sum%10);
        newTail->next=newnode;
        newTail=newTail->next;
        sum/=10;
    }
    ListNode *ret=newHead->next;
    free(newHead);
    newHead=newTail=NULL;
    return ret;
}

typedef struct ListNode ListNode;

ListNode* buynode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* newHead, * newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    int sum = 0;
    int carry = 0;
    while (p1 || p2)
    {
        int n = p1 ? p1->val : 0;
        int m = p2 ? p2->val : 0;
        sum = n + m + carry;
        ListNode* newnode = buynode(sum % 10);
        carry = sum / 10;
        newTail->next = newnode;
        newTail = newTail->next;
        if (p1)
            p1 = p1->next;
        if (p2)
            p2 = p2->next;
    }
    if (carry > 0)
    {
        ListNode* newnode = buynode(carry);
        newTail->next = newnode;
    }
    return newHead->next;
}